package com.cqs.leetcode.dp;

import java.util.HashMap;
import java.util.Map;

/**
 * @author lixiaowen
 * @create 2020-01-10
 */
public class UniqueBinarySearchTrees96 {
    static class Solution0 {

        private Map<Integer, Integer> map = new HashMap<Integer, Integer>() {{
            put(0, 1);
            put(1, 1);
            put(2, 2);
        }};


        public int numTrees(int n) {
            if (map.containsKey(n)) return map.get(n);
            int sum = 0;
            for (int i = 0; i <= n - 1; i++) {
                sum += numTrees(i) * numTrees(n - 1 - i);
            }
            map.put(n, sum);
            return sum;
        }

    }

    static class Solution {

        /**
         * 从中序遍历来看,遍历的结果是1...n.
         * 分别以第一个,第二个...第K个,...第n个元素为根,左右子树元素个数就确定了
         * f(0)*f(n-1) + f(1)f(n-2)+...+f(n-1)*f(0)
         *
         * @param n
         * @return
         */
        public int numTrees(int n) {
            if (n == 0) return 1;
            int[] f = new int[n + 1];
            f[0] = f[1] = 1;
            for (int i = 2; i <= n; i++) {
                //求和
                for (int j = 0; j < i; j++) {
                    f[i] += f[j] * f[i - j - 1];
                }
            }
            return f[n];
        }

    }


    public static void main(String[] args) {
        Solution solution = new Solution();
        for (int i = 0; i < 10; i++) {
            System.out.println(i + "\t result:" + solution.numTrees(i));
        }


    }
}
